710E - Generate a String - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for(int i =(a); i < (b); ++i)
#define re(i, n) FOR(i, 1, n)
#define ford(i, a, b) for(int i = (a); i >= (b); --i)
#define rep(i, n) for(int i = 0;i <(n); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

using namespace std;

typedef long long ll;
typedef pair<ll, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

const ll inf = 1e18;
const int maxn = 5005;

vi dp;

struct min_queue
{
	deque<ll> mono;
	queue<ll> q;
	bool is_empty() {return q.empty();}
	ll get_min() {return mono.front();}
	void push(ll v)
	{
		q.push(v);
		while (!mono.empty() && mono.back() >= v) mono.pop_back();
		mono.push_back(v);
	}
	void pop()
	{
		int v = q.front();
		q.pop();
		if (mono.front() == v) mono.pop_front();
	}
};

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	ll x, y;
	cin >> n >> x >> y;
	dp.resize(n+1);
	dp[0] = 0;
	min_queue q;
	for (ll i = 1; i <= n; i++)
	{
		dp[i] = dp[i-1] + x;
		while (q.q.size() > i/2) q.pop();
		if (!q.is_empty())
		{
			ll dupa = q.get_min();
			dp[i] = min(dp[i], dupa + y - i*x);
		}
		q.push(2*i*x + dp[i]);
	}
	cout << dp[n] << '\n';
}